import java.util.*;

public class BinaryTree {

    public static void main(String[] args) {
        Thread t = new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("1");
            }
        });
        t.start();
        System.out.println("2");

    }

    public static int getLCA(int a, int b) {
        // write code here
        if (a == 1 || b == 1) return 1;
        if (a == b) {
            return a;
        }else if(a > b) {
            a = a / 2;
            return getLCA(a,b);
        }else {
            b = b / 2;
            return getLCA(a,b);
        }
    }

    // 创建一颗二叉树
    public TreeNode create(){
        TreeNode A = new TreeNode(5);
        TreeNode B = new TreeNode(4);
        TreeNode C = new TreeNode(8);
        TreeNode D = new TreeNode(11);
        TreeNode E = new TreeNode(13);
        TreeNode F = new TreeNode(4);
        TreeNode G = new TreeNode(7);
        TreeNode H = new TreeNode(2);
        TreeNode I = new TreeNode(5);
        TreeNode J = new TreeNode(1);
        A.left = B;
        A.right = C;
        B.left = D;
        C.left = E;
        C.right = F;
        D.left = G;
        D.right = H;
        F.left = I;
        F.right = J;
        return A;
    }

    // 先序遍历
    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    public void midOrder(TreeNode root){
        if (root == null){
            return;
        }
        midOrder(root.left);
        System.out.print(root.val + " ");
        midOrder(root.right);
    }

    // 后序遍历
    public void lastOrder(TreeNode root){
        if (root == null){
            return;
        }
        lastOrder(root.left);
        lastOrder(root.right);
        System.out.print(root.val + " ");
    }

    // 求节点数
    public int size(TreeNode root){
        if (root == null) {
            return 0;
        }
        int left = size(root.left);
        int right = size(root.right);
        return left + right + 1;
    }

    // 获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root){
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    // 获取第 K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if (root == null) return 0;
        if (k == 1) return 1;
        int left = getKLevelNodeCount(root.left,k-1);
        int right = getKLevelNodeCount(root.right,k-1);
        return left + right;
    }

    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if (root == null) return 0;

        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left,right) + 1;
    }
    // 检测值为 val 的元素是否存在
    public TreeNode find(TreeNode root, char val){
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode ret = find(root.left,val);
        if (ret != null){
            return ret;
        }
        ret = find(root.right, val);
        if (ret != null) return ret;
        return null;
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek() != null) {
            TreeNode top = queue.poll();
            queue.offer(top.left);
            queue.offer(top.right);
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }

    // 比较两棵二叉树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (q == null && p == null) return true;
        if (q == null || p == null) return false;
        if (p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    // 是否为子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot == null) return true;
        if(root == null) return false;

        if (isSameTree(root,subRoot)) return true;

        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    // 是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int left = getHeight2(root.left);
        int right = getHeight2(root.right);
        if(left < 0 || right < 0) return false;
        return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    // 获取二叉树的高度
    public int getHeight2(TreeNode root){
        if (root == null) return 0;
        int left = getHeight2(root.left);
        int right = getHeight2(root.right);
        if(left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
            return Math.max(left,right) + 1;
        }
        return -1;
    }

    public boolean isBalanced2(TreeNode root) {
        if(root == null){
            return true;
        }

        return getHeight(root) >= 0;
//        int left = getHeight2(root.left);
//        int right = getHeight2(root.right);
//        if (left >= 0 && right >= 0){
//            return Math.abs(left - right) <= 1;
//        }else{
//            return false;
//        }
    }


    // 对称二叉树
    public boolean isSameChild(TreeNode left,TreeNode right) {
        if (left == null && right == null){
            return true;
        }
        if ((left == null && right != null) || (right == null && left != null)){
            return false;
        }
        if (right.val != left.val){
            return false;
        }
        return isSameChild(left.left,right.right) && isSameChild(left.right,right.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSameChild(root.left,root.right);
    }


    //  二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size > 0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    public void levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return;
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(queue.poll() + " ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(root.right);
            }
        }
    }


    // 根据先序遍历出来的字符串创建二叉树
    public int i = 0;
    public TreeNode recoverFromPreorder(String str){
        TreeNode node = null;
        if(str.charAt(i) != '#'){
            node = new TreeNode(str.charAt(i));
            i++;
            node.left = recoverFromPreorder(str);
            node.right = recoverFromPreorder(str);
        }else{
            i++;
        }
        return node;
    }

    // 合并两个二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }

    // 最近公共祖先 --- 搜索树的变相
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();

        // 分别得到  p q 的路径
        getPath(root,p,stackp);
        getPath(root,q,stackq);

        int sizep = stackp.size();
        int sizeq = stackq.size();

        if(sizep > sizeq) {
            int size = sizep - sizeq;
            // 弹出元素直至两栈中元素个数相等
            while(size > 0) {
                stackp.pop();
                size--;
            }
        }else {
            int size = sizeq - sizep;
            // 弹出元素直至两栈中元素个数相等
            while(size > 0) {
                stackq.pop();
                size--;
            }
        }

        // 一起弹出，直到找到第一个相同的元素
        while(!stackp.isEmpty() && !stackq.isEmpty()) {
            if(stackp.peek() == stackq.peek()) {
                return stackq.pop();
            }else {
                stackp.pop();
                stackq.pop();
            }
        }
        return null;
    }
    // 存放从root节点到node节点的路径
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null || node == null) {
            return false;
        }
        // 将当前节点放入栈中
        stack.push(root);

        if(root.val == node.val) {
            return true;// 找到了
        }
        // 当前节点没找到，去左子树找
        boolean flag = getPath(root.left,node,stack);
        // 左子树中找到了，直接返回
        if(flag) {
            return true;
        }
        // 左子树没找到，去右子树找
        flag = getPath(root.right,node,stack);
        // 右子树中找到了，直接返回
        if(flag) {
            return true;
        }

        // 左右子树都没找到，弹出节点
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        while (!stackP.isEmpty() && !stackQ.isEmpty()){
            if (stackP.size() > stackQ.size()){
                int size = stackP.size() - stackQ.size();
                while (size != 0){
                    stackP.pop();
                    size--;
                }
                while (!stackP.isEmpty() && !stackQ.isEmpty()){
                    if (stackP.peek() == stackQ.peek()){
                        return stackP.pop();
                    }else{
                        stackP.pop();
                        stackQ.pop();
                    }
                }
            }else{
                int size = stackQ.size() - stackP.size();
                while (size != 0){
                    stackQ.pop();
                    size--;
                }
                while (!stackP.isEmpty() && !stackQ.isEmpty()){
                    if (stackP.peek() == stackQ.peek()){
                        return stackP.pop();
                    }else{
                        stackP.pop();
                        stackQ.pop();
                    }
                }
            }
        }
        return null;
    }


//    // 将搜索二叉树变为升序的双向链表 --- 中序遍历
//    TreeNode prev = null;
//    public void preSort(TreeNode root){
//        if(root == null) return;
//        preSort(root.left);
//
//        root.left = prev;
//        if(prev != null){
//            prev.right = root;
//        }
//        prev = root;
//
//        preSort(root.right);
//    }
//    public TreeNode Convert(TreeNode pRootOfTree) {
//        if(pRootOfTree == null || (pRootOfTree.left == null && pRootOfTree.right == null)){
//            return pRootOfTree;
//        }
//        preSort(pRootOfTree);
//        TreeNode cur = pRootOfTree;
//        while(cur.left != null){
//            cur = cur.left;
//        }
//        return cur;
//    }


    // 根据二叉树的先序遍历 和 中序遍历，请构造二叉树并返回其根节点。

    int rootIndex = 0;
    public TreeNode createRootFromInOder(int[] preorder, int[] inorder,int begin,int end) {
        if (begin > end) return null;
        int index = findRoot(inorder,preorder[rootIndex]);
        if (index >= 0){
            TreeNode root = new TreeNode(inorder[index]);
            rootIndex++;
            root.left = createRootFromInOder(preorder,inorder,begin,index-1);
            root.right = createRootFromInOder(preorder,inorder,index+1,end);
            return root;
        }else{
            return null;
        }
    }
    public int findRoot(int[] inorder,int rootNUm) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootNUm) return i;
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null && inorder == null) return null;
        return createRootFromInOder(preorder,inorder,0,preorder.length-1);
    }


    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> deque = new LinkedList<>();
        int maxSize = 1;
        deque.offer(root);
        while (!deque.isEmpty()){
        int width = deque.size();
        int tempWidth = deque.size();
        int nullNum = 0;
        while (width > 0){
            TreeNode cur = deque.poll();
            if (width == 1 || width == tempWidth){
                width--;
                continue;
            }
            if (cur != null){
                deque.offer(cur.left);
                deque.offer(cur.right);
            }else{
                nullNum += 2;
            }
            width--;
        }
//            while (!deque.isEmpty() && deque.peekLast() == null){
//                deque.pollLast();
//            }
//            while (!deque.isEmpty() && deque.peekFirst() == null){
//                deque.pollFirst();
//            }
            maxSize = Math.max(maxSize,deque.size() + nullNum);
        }
        return maxSize;
    }

    public TreeNode increasingBST(TreeNode root) {
        if (root == null) return null;
        TreeNode leftRoot = increasingBST(root.left);
        root.right = increasingBST(root.right);
        if (leftRoot == null) return root;
        TreeNode cur = leftRoot;
        while (cur.right != null){
            cur = cur.right;
        }
        root.left = null;
        cur.right = root;
        return leftRoot;
    }


    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        inOrder(pRootOfTree);
        TreeNode cur = pRootOfTree;
        while(cur.left != null){
            cur = cur.left;
        }
        return cur;
    }
    TreeNode prev = null;
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        if (prev != null){
            prev.right = root;
        }
        root.left = prev;
        prev = root;
        inOrder(root.right);
    }



}
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}